#ifndef JUMP_POINT_SEARCH_HPP
#define JUMP_POINT_SEARCH_HPP

////////////////////////////////////////////////////////////
// Headers
////////////////////////////////////////////////////////////
#include "BasePathfindingAlgorithm.hpp"

#include <SmegTools/Debug/DebugNew.hpp>

namespace smeg {
    namespace ai {
////////////////////////////////////////////////////////////
/// Base class for Pathfinding algorithm
////////////////////////////////////////////////////////////
class JumpPointSearch : public BasePathfindingAlgorithm
{
public:
    ////////////////////////////////////////////////////////////
    /// Constructor/Destructor
    ////////////////////////////////////////////////////////////
                                JumpPointSearch( Grid* _pGrid );
    virtual                     ~JumpPointSearch();

    ////////////////////////////////////////////////////////////
    /// Find a path between start and end
    ///
    /// \param _Start : Start point 
    /// \param _End :   End point 
    ///
    ////////////////////////////////////////////////////////////
    virtual const std::vector< sf::Vector2f >& FindPath( const sf::Vector2f& _Start, const sf::Vector2f& _End );

protected:
    ////////////////////////////////////////////////////////////
    /// Constructor
    ////////////////////////////////////////////////////////////
                                JumpPointSearch();

    ////////////////////////////////////////////////////////////
    /// Find a node to jump from the given one in the given direction
    ///
    /// \param _iNodeX :        Current node X position
    /// \param _iNodeY :        Current node Y position
    /// \param _iDirX :         X Direction to jump
    /// \param _iDirY :         Y Direction to jump
    /// \param _pStartNode :    Start node
    /// \param _pEndNode :      End node
    ///
    ////////////////////////////////////////////////////////////
    Node*                       Jump( int _iNodeX, int _iNodeY,
                                        int _iDirX, int _iDirY,
                                        Node* _pStartNode, Node* _pEndNode );

    ////////////////////////////////////////////////////////////
    /// Find the interesting neighbours for the current node
    ///
    /// \param _pCurrentNode :  Current node
    /// \param _Neighbours :    All interesting neighbours of this node
    ///
    ////////////////////////////////////////////////////////////
    void                        FindInterestingNeighbours( Node* _pCurrentNode,
                                        std::vector< Node* >& _Neighbours );

    ////////////////////////////////////////////////////////////
    /// Find the possible successors for the current node
    ///
    /// \param _pCurrentNode :  Current node
    /// \param _pStartNode :    Start node
    /// \param _pEndNode :      End node
    /// \param _Successors :    All successors of this node
    ///
    ////////////////////////////////////////////////////////////
    void                        FindSuccessors( Node* _pCurrentNode, 
                                        Node* _pStartNode, 
                                        Node* _pEndNode,
                                        std::vector< Node* >& _Successors );

#ifdef _DEBUG
public:
    bool                        DebugStartPath( const sf::Vector2f& _Start, const sf::Vector2f& _End );
    bool                        DebugStepPath( const sf::Vector2f& _Start, const sf::Vector2f& _End );
#endif
};

    } // namespace ai
} // namespace smeg

#include <SmegTools/Debug/DebugNewOff.hpp>

#endif // JUMP_POINT_SEARCH_HPP
